package cn.kent.simple;

/**
 * 303. 区域和检索 - 数组不可变
 * 第一种，笨方法，51ms+
 * 第二种，前缀和，初始化先计算前缀和，放到新数组中，计算时直接取值相减，时间复杂度O(1)
 */
public class NumArray {

    /*private int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int left, int right) {
        int sum=0;
        for (int i = left; i <= right; i++) {
            sum += this.nums[i];
        }
        return sum;
    }*/

    /**
     * 前缀和
     */
    private int[] sums;

    public NumArray(int[] nums) {
        // 将每个前缀求和放到新数组中，求和的时候直接 sums[right]-sums[left]
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = nums[i] + sums[i];
        }
    }

    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}
